<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="NOhnM" id="NOhnM"><span data-lake-id="u9c0cebb5" id="u9c0cebb5">典型回答</span></h1>
  <p data-lake-id="u8c512957" id="u8c512957"><br></p>
  <p data-lake-id="u36b372c7" id="u36b372c7"><span data-lake-id="u3b5e65bd" id="u3b5e65bd">hash join</span><span data-lake-id="uc0a26c33" id="uc0a26c33" class="lake-fontsize-11" style="color: rgb(34, 34, 34)"> 是 MySQL 8.0.18版本中新推出的一种多表join的算法。</span></p>
  <p data-lake-id="u557e029d" id="u557e029d"><span data-lake-id="uff0fa190" id="uff0fa190">​</span><br></p>
  <p data-lake-id="u8cf0139e" id="u8cf0139e"><span data-lake-id="u51fc8abd" id="u51fc8abd">在这之前，MySQL是使用了嵌套循环（Nested-Loop Join）的方式来实现关联查询的，而嵌套循环的算法其实性能是比较差的，而Hash Join的出现就是要优化Nested-Loop Join的。</span></p>
  <p data-lake-id="ubd452d2d" id="ubd452d2d"><span data-lake-id="ub3fccbad" id="ub3fccbad">​</span><br></p>
  <p data-lake-id="ue6513a19" id="ue6513a19"><br></p>
  <p data-lake-id="u133c52c6" id="u133c52c6"><strong><span data-lake-id="u7c244f81" id="u7c244f81">所谓Hash Join，其实是因为他底层用到了Hash表。</span></strong></p>
  <p data-lake-id="u8a0fa02d" id="u8a0fa02d"><strong><span data-lake-id="u6817eef1" id="u6817eef1">​</span></strong><br></p>
  <p data-lake-id="ufd32a878" id="ufd32a878"><span data-lake-id="u3a42fb8c" id="u3a42fb8c">Hash Join 是一种针对 equal-join 场景的优化，他的基本思想是将驱动表数据加载到内存，并建立 hash 表，这样只要遍历一遍非驱动表，然后再去通过哈希查找在哈希表中寻找匹配的行</span><span data-lake-id="u1a7aa694" id="u1a7aa694" class="lake-fontsize-12" style="color: rgb(55, 65, 81); background-color: rgb(247, 247, 248)"> </span><span data-lake-id="u50527a12" id="u50527a12">，就可以完成 join 操作了。</span></p>
  <p data-lake-id="u127fd799" id="u127fd799"><span data-lake-id="uf08bbe5c" id="uf08bbe5c">​</span><br></p>
  <p data-lake-id="ud6adef1e" id="ud6adef1e"><span data-lake-id="u8dba0e80" id="u8dba0e80">举个栗子。</span></p>
  <p data-lake-id="u778f9a3c" id="u778f9a3c"><span data-lake-id="u46995992" id="u46995992">​</span><br></p>
  <pre lang="java"><code>
SELECT
  student_name,school_name
FROM
  students LEFT JOIN schools ON students.school_id=schools.id;
</code></pre>
  <p data-lake-id="u663ff490" id="u663ff490"><br></p>
  <p data-lake-id="u35f5756d" id="u35f5756d"><span data-lake-id="ud0beed4b" id="ud0beed4b">以上，是一个left join的SQL，</span><strong><span data-lake-id="u7909cee2" id="u7909cee2">在Hash Join过程中，主要分为两个步骤，分别是构建和探测</span></strong><span data-lake-id="u07caf19f" id="u07caf19f">。</span></p>
  <p data-lake-id="u5f5c9d47" id="u5f5c9d47"><span data-lake-id="u2fb16962" id="u2fb16962">​</span><br></p>
  <p data-lake-id="u5bf53684" id="u5bf53684"><span data-lake-id="ue73ac867" id="ue73ac867">构建阶段，假如优化器优化后使用students作为驱动表，那么就会把这个驱动表的数据构建到hash表中：</span></p>
  <p data-lake-id="u257fc53b" id="u257fc53b"><span data-lake-id="uaa0e8182" id="uaa0e8182">​</span><br></p>
  <p data-lake-id="u0de64195" id="u0de64195"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1685435976145-4815d9d3-9a52-4e86-93ad-c05b55933a8d.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_66%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u2dc04854" id="u2dc04854"><span data-lake-id="ue9c1fa07" id="ue9c1fa07">​</span><br></p>
  <p data-lake-id="u7abd83a6" id="u7abd83a6"><span data-lake-id="ua0068bda" id="ua0068bda">探测阶段，在这个过程中，从school表中取出记录之后，去hash表中查询，找到匹配的数据，在做聚合就行了。</span></p>
  <p data-lake-id="u6a23b966" id="u6a23b966"><span data-lake-id="u33c3f112" id="u33c3f112">​</span><br></p>
  <p data-lake-id="u93c53712" id="u93c53712"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1685436088989-f24aa811-27e1-4c2a-862d-9dd80b6ccc95.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_68%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u751551f7" id="u751551f7"><br></p>
  <p data-lake-id="ua18d775d" id="ua18d775d"><span data-lake-id="u8cb7182c" id="u8cb7182c">需要注意的时候，上面的Hash表是在内存中的，但是，内存是有限的（通过join_buffer_size限制），如果内存中存不下驱动表的数据怎么办呢？</span></p>
  <h1 data-lake-id="hEu1z" id="hEu1z"><span data-lake-id="u06fac7d6" id="u06fac7d6" style="color: rgb(85, 85, 85)">扩展知识</span></h1>
  <p data-lake-id="ue3fc96f5" id="ue3fc96f5"><br></p>
  <h2 data-lake-id="oxPnj" id="oxPnj"><span data-lake-id="u43193558" id="u43193558">基于磁盘的hash join</span></h2>
  <p data-lake-id="u7b1c22da" id="u7b1c22da"><br></p>
  <p data-lake-id="ud06c163e" id="ud06c163e"><span data-lake-id="ud3b99cf9" id="ud3b99cf9">如果驱动表中的数据量比较大， 没办法一次性的加载到内存中，就需要考虑把这些数据存储在磁盘上。通过将哈希表的一部分存储在磁盘上，分批次地加载和处理数据，从而减少对内存的需求。</span></p>
  <p data-lake-id="ua8e874b9" id="ua8e874b9"><span data-lake-id="uc6b2a0b8" id="uc6b2a0b8">​</span><br></p>
  <p data-lake-id="ucf59b98b" id="ucf59b98b"><span data-lake-id="u9afc203f" id="u9afc203f">在这样的算法中，为了避免一个大的hash表内存中无法完全存储，那么就采用分表的方式来实现，即首先利用 hash 算法将驱动表进行分表，并产生临时分片写到磁盘上。</span></p>
  <p data-lake-id="u5903ca83" id="u5903ca83"><span data-lake-id="uf72b3acb" id="uf72b3acb">​</span><br></p>
  <p data-lake-id="u7e67eb66" id="u7e67eb66"><span data-lake-id="u5c6f980c" id="u5c6f980c">这样就相当于把一张驱动表，拆分成多个hash表，并且分别存储在磁盘上。</span></p>
  <p data-lake-id="ua677396a" id="ua677396a"><span data-lake-id="u3df9b109" id="u3df9b109">​</span><br></p>
  <p data-lake-id="ue37f3aaa" id="ue37f3aaa"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1685603604500-110a7c08-b237-40fa-937b-96d6362e469f.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_69%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u43f83958" id="u43f83958"><span data-lake-id="u915e9530" id="u915e9530">​</span><br></p>
  <p data-lake-id="ucbace35e" id="ucbace35e"><span data-lake-id="u5ae36cff" id="u5ae36cff">接下来就是做join了，在这个过程中，会对被驱动表使用同样的 hash 算法进行分区，确定好在哪个分区之后，先确认下这个分区是否已经加载到内存，如果已经加载，则直接在内存中的哈希表中进行查找匹配的行。</span></p>
  <p data-lake-id="u77c361ac" id="u77c361ac"><span data-lake-id="u21ae195f" id="u21ae195f">​</span><br></p>
  <p data-lake-id="ua3a7c6f8" id="ua3a7c6f8"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1685603699774-915d7798-d81f-4ea1-bbb3-9518e0f9f613.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_48%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u801a84ea" id="u801a84ea"><br></p>
  <p data-lake-id="ubaaeced0" id="ubaaeced0"><span data-lake-id="u8fc998b3" id="u8fc998b3">如果哈希值对应的分区尚未加载到内存中，则从磁盘上读取该分区的数据到内存中的哈希表，并进行匹配。</span></p>
  <p data-lake-id="u0ddfae98" id="u0ddfae98"><span data-lake-id="u6703124b" id="u6703124b">​</span><br></p>
  <p data-lake-id="u578f695f" id="u578f695f"><span data-lake-id="u40c1e7c1" id="u40c1e7c1">就这样不断的重复进行下去，直到把所有数据都join完，把结果集返回。</span></p>
  <p data-lake-id="u5978b69e" id="u5978b69e"><span data-lake-id="u5b941748" id="u5b941748">​</span><br></p>
  <p data-lake-id="u07d34fb4" id="u07d34fb4"><span data-lake-id="uc9d58469" id="uc9d58469">​</span><br></p>
 </body>
</html>